package com.aug_leo.datastructure.linkedlist;

/**
 * 删除有序链表重复元素
 */
public class E04Leetcode83 {

    /**
     * <h3>方法一</h3>
     * 删除排序链表中的重复元素
     * 如果链表中存在重复的元素，该方法将删除这些重复的元素，使链表只包含唯一元素
     *
     * @param head 链表的头节点如果头节点为空或链表仅有一个节点，则不需要进行任何操作
     * @return 处理后的链表头节点
     */
    public ListNode deleteDuplicates1(ListNode head) {
        // 节点数 < 2
        if (head == null || head.next == null) {
            return head;
        }
        // 节点数 >= 2
        ListNode pointer1 = head;
        ListNode pointer2;
        while ((pointer2 = pointer1.next) != null) {
            if (pointer1.val == pointer2.val) {
                // 删除pointer2
                pointer1.next = pointer2.next;
            } else {
                // 向后平移
                pointer1 = pointer1.next;
            }
        }
        return head;
    }

        /*
        梳理流程：
            deleteDuplicates(ListNode p = 1) {
                deleteDuplicates(ListNode p = 1) {
                    deleteDuplicates(ListNode p = 2) {
                        deleteDuplicates(ListNode p = 3) {
                            deleteDuplicates(ListNode p = 3) {
                                // 只剩一个节点，返回
                            }
                        }
                    }
                }
            }
     */

    /**
     * <h3>方法二 递归</h3>
     * 删除排序链表中的所有重复元素，使每个元素只出现一次
     * 1、若我与next重复，返回next
     * 2、若我与next不重复，返回我，但next应当更新
     *
     * @param pointer 链表的头指针
     * @return 删除重复元素后的链表头指针
     */
    public ListNode deleteDuplicates(ListNode pointer) {
        // 如果链表为空或只有一个元素，则直接返回，无需处理重复元素
        if (pointer == null || pointer.next == null) {
            return pointer;
        }
        // 如果当前节点和下一个节点的值相同，则移除当前节点
        if (pointer.val == pointer.next.val) {
            return deleteDuplicates(pointer.next);
        } else {
            // 如果当前节点和下一个节点的值不同，则保留当前节点
            pointer.next = deleteDuplicates(pointer.next);
            return pointer;
        }
    }


    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 1, 2, 3, 3);
        System.out.println(head);
        System.out.println(new E04Leetcode83().deleteDuplicates(head));
    }
}
